#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int sum[N];
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s; // 1-based index

    // 前缀和，sm[i]表示前i个字符中0的个数
    for (int i = 1; i <= n; ++i)
      sum[i] = sum[i - 1] + 1 - s[i] + '0';

    int ans = n - sum[n], mn = n;
    // i-1-sum[i-1] + (sum[j]-sum[i-1]) + n-j-(sum[n]-sum[j] )
    // = {i-1-2* sum[i-1]} + {n-j- sum[n]+sum[j]+sum[j]}
    for (int i = n; i >= 1; --i) {
      mn = min(mn, n - i - sum[n] + 2 * sum[i]);
      ans = min(ans, i - 1 - 2 * sum[i - 1] + mn);
    }
    cout << ans << endl;
  }
  return 0;
}